'''
https://leetcode.cn/problems/max-value-of-equation/description/
'''
from collections import deque
from typing import List


class Solution:
    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
        ans = float('-inf')
        monotonic_q = deque()   # 从左往右，从大到小
                                # 存放的东西为 y-x, 要求的东西为 y2+x2+y1-x1
                                # 当来到某点，计算取到这个指标为最大的就是自己要的最好的点
        for x, y in points:
            # 缩小窗口，剔除掉过期的点
            while monotonic_q and monotonic_q[0][0] + k < x:
                monotonic_q.popleft()

            # 如果有好的指标，且不能是自己
            # print(x,y,monotonic_q)
            if monotonic_q:
                ans = max(ans, y + x + monotonic_q[0][1] - monotonic_q[0][0])

            # 当前点入队列，同时维护队列的那个指标 从大到小的排列
            while monotonic_q and y - x >= monotonic_q[-1][1] - monotonic_q[-1][0]:
                monotonic_q.pop()
            monotonic_q.append([x, y])
        return ans

